package com.summli.basic.class04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 引用类型的堆结构
 */
public class Code03_Heap02 {

    public static class MyHeap<T>{
        private ArrayList<T> heap;//保存堆元素
        private HashMap<T,Integer> indexMap;//保存的堆元素对应的坐标索引
        private int heapSize;
        private Comparator<T> comparator;

        public MyHeap(Comparator<T> comparator) {
            this.comparator = comparator;
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
            heapSize = 0;
        }

        public boolean isEmpty(){
            return heapSize == 0;
        }

        public boolean contains(T t){
            return indexMap.containsKey(t);
        }

        public int size(){
            return heapSize;
        }


        // 如果是引用类型的话，堆结构建立好之后，如果改变了堆结构中的元素的成员属性值，需要提供一个resign方法维护结构
        public void resign(T value){
            if(!contains(value)){
                throw new RuntimeException("heap not having the value!");
            }
            int index = indexMap.get(value);
            heapInsert(index);
            heapify(heap, index, heapSize);
        }

        //pop方法
        public T pop(){
            if(isEmpty()){
                throw new RuntimeException("heao is empty");
            }
            T result = heap.get(0);
            swap(heap, 0, --heapSize);
            heapify(heap,0,heapSize);
            return result;
        }

        private void heapify(ArrayList<T> heap,int index, int heapSize) {
            int left = 2*index +1;
            while(left<heapSize){
                int large = left+1 < heapSize &&
                        comparator.compare(heap.get(left+1), heap.get(left)) <0? left+1:left;
                large = comparator.compare(heap.get(index),heap.get(large))<0?index:large;
                if(large == index)break;
                swap(heap,index,large);
                indexMap.put(heap.get(index),index);
                indexMap.put(heap.get(large),large);
                index = large;
                left = 2*index +1;
            }
        }

        // push方法
        public void push(T value){
            heap.add(value);
            indexMap.put(value, heapSize);
            heapInsert(heapSize++);
        }

        private void heapInsert(int index) {
            while(comparator.compare(heap.get(index),heap.get((index-1)/2)) <0){
                swap(heap,index,(index-1)/2);
                indexMap.put(heap.get(index),index);
                indexMap.put(heap.get((index-1)/2),(index-1)/2);
                index = (index-1)/2;
            }
        }

        private void swap(ArrayList<T> heap, int i, int j) {
            T temp = heap.get(i);
            heap.set(i, heap.get(j));
            heap.set(j,temp);
        }

    }
    public static class Student {
        public int classNo;
        public int age;
        public int id;

        public Student(int c, int a, int i) {
            classNo = c;
            age = a;
            id = i;
        }

    }

    public static class StudentComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o2.age - o1.age;
        }

    }

    public static void main(String[] args) {
        Student s1 = null;
        Student s2 = null;
        Student s3 = null;
        Student s4 = null;
        Student s5 = null;
        Student s6 = null;

        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);

        PriorityQueue<Student> heap = new PriorityQueue<>(new StudentComparator());
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        heap.add(s6);
        while (!heap.isEmpty()) {
            Student cur = heap.poll();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }

        System.out.println("===============");

        MyHeap<Student> myHeap = new MyHeap<>(new StudentComparator());
        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);
        myHeap.push(s5);
        myHeap.push(s6);
        while (!myHeap.isEmpty()) {
            Student cur = myHeap.pop();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }

        System.out.println("===============");

        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);

        heap = new PriorityQueue<>(new StudentComparator());

        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        heap.add(s6);

        s2.age = 6;
        s4.age = 12;
        s5.age = 10;
        s6.age = 84;

        while (!heap.isEmpty()) {
            Student cur = heap.poll();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }

        System.out.println("===============");

        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);

        myHeap = new MyHeap<>(new StudentComparator());

        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);
        myHeap.push(s5);
        myHeap.push(s6);

        s2.age = 6;
        myHeap.resign(s2);
        s4.age = 12;
        myHeap.resign(s4);
        s5.age = 10;
        myHeap.resign(s5);
        s6.age = 84;
        myHeap.resign(s6);

        while (!myHeap.isEmpty()) {
            Student cur = myHeap.pop();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }


    }


}
